package basic.study.algorithms.sort;

import java.util.Arrays;

public class Sorts1 {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 2, 5, 12, 3};
        quickSort4(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
//        int k = 3;
//        System.out.println(sort(arr, 0, arr.length -1, k));
    }
    //归并排序
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int q = (left + right) / 2;
        mergeSort(arr, left, q);
        mergeSort(arr, q+1, right);
        merge2(arr, left, q, right);
    }

    public static void merge2(int[] arr, int left, int q, int right) {
        int[] leftArr = new int[q - left + 2];
        int[] rightArr = new int[right - q + 1];

        for (int i = 0; i <= q - left; i++) {
            leftArr[i] = arr[left + i];
        }
        leftArr[q - left + 1] = Integer.MAX_VALUE;

        for (int i = 0; i < right - q; i++) {
            rightArr[i] = arr[q + 1 + i];
        }
        rightArr[right - q] = Integer.MAX_VALUE;

        int i = 0;
        int j = 0;
        int k = left;
        while (k <= right) {
            if(leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }
    }
    //快排
    public static void quickSort(int[] arr, int left ,int right) {
        if(left >= right) return;

        int p = partition2(arr, left, right);
        quickSort(arr, left, p-1);
        quickSort(arr, p+1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if(arr[j] < pivot) {
                if (i == j) {
                    i++;
                } else {
                    int temp = arr[i];
                    arr[i++] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        int temp = arr[right];
        arr[right] = arr[i];
        arr[i] = temp;
        return i;
    }
    //三数取中法 , 随机数在这里写
    public static int partition2(int[] arr, int left, int right) {
        int middle = (left + right) / 2;
        int pivot = arr[middle];
        int temp1 = arr[right];
        arr[right] = arr[middle];
        arr[middle] = temp1;

        int i = left;
        for (int j = left; j < right; j++) {
            if(arr[j] < pivot) {
                if (i == j) {
                    i++;
                } else {
                    int temp = arr[i];
                    arr[i++] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        int temp = arr[right];
        arr[right] = arr[i];
        arr[i] = temp;
        return i;
    }
    //三向切分快速排序，中间为相等的区间，解决大量重复的数据
    public static void quickSort3(int[] arr, int left, int right) {
        if (left >= right) return;

        int l = left;
        int k = left + 1;
        int r = right;
        int pivot = arr[l];

        while (k <= r) {
            if (arr[k] < pivot) {
                int tmp = arr[l];
                arr[l] = arr[k];
                arr[k] = tmp;
                l++;
                k++;
            } else if (arr[k] == pivot) {
                k++;
            } else {
                if (arr[r] > pivot) {
                    r--;
                } else if (arr[r] == pivot) {
                    int tmp = arr[k];
                    arr[k] = arr[r];
                    arr[r] = tmp;
                    k++;
                    r--;
                } else {
                    int tmp = arr[l];
                    arr[l] = arr[r];
                    arr[r] = arr[k];
                    arr[k] = tmp;
                    l++;
                    k++;
                    r--;
                }
            }
        }
        quickSort3(arr, left, l-1);
        quickSort3(arr, r+1, right);
    }
    /**
     * 双轴快速排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private static void quickSort4(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int l = left;
        int k = left + 1;
        int r = right;
        // 判断pivot1 与 pivot2 大小
        if (arr[l] > arr[r]) {
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
        }
        int pivot1 = arr[l];
        int pivot2 = arr[r];

        while (k < r) {
            if(arr[k] < pivot1) {
                l++;
                if (l != k) {
                    int tmp = arr[l];
                    arr[l] = arr[k];
                    arr[k] = tmp;
                }
                k++;
            } else if (arr[k] >= pivot1 && arr[k] <= pivot2) {
                k++;
            } else {
                --r;
                if (arr[r] > pivot2) {

                } else if (arr[r] >= pivot1 && arr[r] <= pivot2) {
                    int tmp = arr[k];
                    arr[k] = arr[r];
                    arr[r] = tmp;
                    k++;
                } else {
                    l++;
                    int tmp = arr[l];
                    arr[l] = arr[r];
                    arr[r] = arr[k];
                    arr[k] = tmp;
                    k++;
                }
            }
        }
        //交换pivot1 和pivot2
        arr[left] = arr[l];
        arr[l] = pivot1;
        arr[right] = arr[r];
        arr[r] = pivot2;

        quickSort4(arr, left, l-1);
        quickSort4(arr, l+1, r-1);
        quickSort4(arr, r+1, right);
    }



    /*
     *  O(n)  时间复杂度内求无序数组中的第 K  大元素。比如， 4 ， 2 ， 5 ， 12 ， 3  这样一组数据，第 3  大元素就是 4 。
     */
    public static int sort(int[] arr, int left, int right, int k) {
        if( left >= right) {
            return 0;
        }
        int q = partition(arr, left, right);
        if(q+1 == k) {
            return arr[q];
        }else if(q+1 > k) {
            return sort(arr, left, q-1, k);
        }else {
            return sort(arr, q+1, right, k);
        }
    }
}
